package 困难;

import java.util.*;

public class 买卖股票的最佳时机 {

    public static void main(String[] args) {
        //2
        //[1,2,4,2,5,7,2,4,9,0]
        int[] prices = {1, 3, 2, 8, 4, 9};
        //System.out.println(maxProfit4(2,prices ));
        System.out.println(maxProfit5(prices,2));
    }

    //最多交易k次 IV
    public static int maxProfit4(int k, int[] prices){

        int length = prices.length;
        if (length<2){
            return 0;
        }
        k = Math.min(k,length/2 );
        int[][][] dp = new int[length][k+1][2];//dp[n][k][0] 意味着第n+1天,最多k次交易,最终手上没有股票的最大收益.
        for (int n = 0; n < length; n++) {
            for (int i = k; i >0; i--) {
                if (n-1==-1){
                    dp[n][i][0] = 0;
                    dp[n][i][1] = -prices[n];
                    dp[n][0][0] = 0;
                    dp[n][0][1] = Integer.MIN_VALUE;
                }else {
                    dp[n][i][0] = Math.max(dp[n-1][i][0],dp[n-1][i][1] + prices[n] );
                    dp[n][i][1] = Math.max(dp[n-1][i][1],dp[n-1][i-1][0] - prices[n]);
                }

            }
        }
        return dp[length-1][k][0];
    }

    //只交易一次
    public static int maxProfit(int[] prices){
        int length = prices.length;
        if (length<2){
            return 0;
        }
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        for (int i = 1; i < length; i++) {
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i] );
            dp_i_1 = Math.max(dp_i_1,-prices[i] );
        }
        return dp_i_0;
    }
    //不限交易次数II
    public static int maxProfit2(int[] prices){
        int length = prices.length;
        if (length<2){
            return 0;
        }
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        int temp;
        for (int i = 1; i < length; i++) {
            temp = dp_i_0;
            dp_i_0 = Math.max(temp,dp_i_1+prices[i] );
            dp_i_1 = Math.max(dp_i_1,temp-prices[i] );
        }
        return dp_i_0;
    }
    //不限交易次数含冷冻期III
    public static int maxProfit3(int[] prices){
        int length = prices.length;
        if (length<2){
            return 0;
        }
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        int temp;
        int dp_pre_0 = 0;
        for (int i = 1; i < length; i++) {
            temp = dp_i_0;
            dp_i_0 = Math.max(temp,dp_i_1+prices[i] );
            dp_i_1 = Math.max(dp_i_1,dp_pre_0-prices[i] );
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }

    //不限交易次数含手续费V
    public static int maxProfit5(int[] prices,int fee){
        int length = prices.length;
        if (length<2){
            return 0;
        }
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        int temp;
        for (int i = 1; i < length; i++) {
            temp = dp_i_0;
            dp_i_0 = Math.max(temp,dp_i_1+prices[i]-fee );
            dp_i_1 = Math.max(dp_i_1,temp-prices[i] );
        }
        return dp_i_0;
    }
}


